Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Analyzing Simple Algorithms

In this lesson, we’ll practice analyzing time complexity using two basic algorithms: finding the maximum element in a list and Insertion Sort. Both examples will reinforce the process of breaking down an algorithm and identifying the time complexity.

Example 1: Finding the Maximum Element in a List

Let’s start with a simple algorithm to find the maximum element in a list of n numbers.

Algorithm Code

Java

. . . .

Step-by-Step Analysis

Image
  1. Initialization: max_num = numbers[0]

    • This assignment is constant and takes time.
  2. Loop through the List: for num in numbers

    • The loop runs once for each element in the list, making it because we’re visiting every element once.
  3. Conditional Check: if num > max_num

    • Inside the loop, the if statement checks each element. Since this check is executed in each iteration, it contributes to the time complexity.
  4. Assignment Inside Loop: max_num = num

    • The assignment only happens when the condition is true. However, it’s still part of the loop, so we consider its complexity as overall.

Total Time Complexity

Adding all these steps together, we get:

  • Initialization:
  • Loop (including conditional check and assignment):

Since , the total time complexity of the find_max algorithm is .

Example 2: Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It’s useful for small or nearly sorted data but can be inefficient for larger lists.

Algorithm Code

Java
Saved to Cloud

. . . .

Step-by-Step Analysis

Image

Let’s break down each part of the code and analyze its time complexity.

  1. Outer Loop: for i in range(1, len(arr))

    • This loop runs from the second element (index 1) to the last element of arr, so it iterates n - 1 times (where n is the length of the array).
    • The outer loop contributes a time complexity of .
  2. Inner Loop: while j >= 0 and arr[j] > key

    • The inner while loop compares arr[j] to key and shifts elements if they are larger than key.
    • In the worst case, the while loop can run i times for each i in the outer loop, especially if the list is in reverse order.
    • On average, for each element, it runs half of i times, resulting in time complexity contributions for each outer loop iteration.
  3. Total Time Complexity

    To understand the full time complexity, let’s examine different cases:

    • When the array is in reverse order, each element is compared with all the previous elements. This results in a maximum of comparisons.
    • This sum simplifies to approximately , giving us a time complexity of .

In the next lesson, Best, Worst, and Average Cases, we’ll explore how different inputs affect the performance of algorithms like insertion sort.

Analyzing Control Structures
Best, Worst, and Average Cases
Mark as Completed

On this page

Example 1: Finding the Maximum Element in a List

Algorithm Code

Step-by-Step Analysis

Example 2: Insertion Sort

Algorithm Code

Step-by-Step Analysis